package arithmetic_40;

/**
 *
 * @author wxh
 */
public class Solution_2 {

	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

		// 如果递归到了空节点，直接返回空即可
		if (root == null) {
			return null;
		}

		// 如果有一个等于root，直接返回root即可
		if (root.equals(p) || root.equals(q)) {
			return root;
		}

		// 如果都不等于root，则分别查找他的左子树和右子树，得到结果值
		TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
		TreeNode rightNode = lowestCommonAncestor(root.right, p, q);

		// 如果左子树没有结果，则返回右子树的结果
		if (leftNode == null) {
			return rightNode;
		}
		// 如果右子树没有结果，则返回左子树的结果
		if (rightNode == null) {
			return leftNode;
		}

		// 如果都不为空，说明root就是p、q的公共祖先
		return root;
	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}

}